SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Linear code</title>

</head>

Linear code

</h1>

</header>

In <a href="Coding_theory" title="Coding theory">coding theory</a>, a linear code is an <a href="Error-correcting_code" class="mw-redirect" title="Error-correcting code">error-correcting code</a> for which any <a href="Linear_combination" title="Linear combination">linear combination</a> of <a href="Code_word_(communication)" title="Code word (communication)">codewords</a> is also a codeword. Linear codes are traditionally partitioned into <a href="Block_code" title="Block code">block codes</a> and <a href="Convolutional_code" title="Convolutional code">convolutional codes</a>, although <a href="Turbo_code" title="Turbo code">turbo codes</a> can be seen as a hybrid of these two types.<a href="#cite_note-1">[1]</a> Linear codes allow for more efficient encoding and decoding algorithms than other codes (cf. <a href="Syndrome_decoding" class="mw-redirect" title="Syndrome decoding">syndrome decoding</a>).

Linear codes are used in <a href="Forward_error_correction" class="mw-redirect" title="Forward error correction">forward error correction</a> and are applied in methods for transmitting symbols (e.g., <a href="Bit" title="Bit">bits</a>) on a <a href="Communications_channel" class="mw-redirect" title="Communications channel">communications channel</a> so that, if errors occur in the communication, some errors can be corrected or detected by the recipient of a message block. The codewords in a linear block code are blocks of symbols that are encoded using more symbols than the original value to be sent.<a href="#cite_note-DrMacKayECC-2">[2]</a> A linear code of length n transmits blocks containing n symbols. For example, the [7,4,3] <a href="Hamming_code" title="Hamming code">Hamming code</a> is a linear <a href="Binary_code" title="Binary code">binary code</a> which represents 4-bit messages using 7-bit codewords. Two distinct codewords differ in at least three bits. As a consequence, up to two errors per codeword can be detected while a single error can be corrected.<a href="#cite_note-Cover_and_Thomas-3">[3]</a> This code contains 24 = 16 codewords.

<div class="mw-heading mw-heading2"><h2 id="Definition_and_parameters">Definition and parameters</h2></div>

A linear code of length n and dimension k is a <a href="Linear_subspace" title="Linear subspace">linear subspace</a> C with <a href="Dimension_(linear_algebra)" class="mw-redirect" title="Dimension (linear algebra)">dimension</a> k of the <a href="Vector_space" title="Vector space">vector space</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{q}^{n}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{q}^{n}}</annotation>

</semantics>

</math><img src="./0a630603c6f2f8f58f5d1fb9ef1b9ad194e258a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:2.639ex; height:3.176ex;" alt="{\displaystyle \mathbb {F} _{q}^{n}}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{q}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{q}}</annotation>

</semantics>

</math><img src="./dbb96e056c071d13fc7702013f9273e7f5cd88a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.409ex; height:2.843ex;" alt="{\displaystyle \mathbb {F} _{q}}" loading="lazy"> is the <a href="Finite_field" title="Finite field">finite field</a> with q elements. Such a code is called a q-ary code. If q = 2 or q = 3, the code is described as a binary code, or a ternary code respectively. The vectors in C are called codewords. The size of a code is the number of codewords and equals qk.

The weight of a codeword is the number of its elements that are nonzero and the distance between two codewords is the <a href="Hamming_distance" title="Hamming distance">Hamming distance</a> between them, that is, the number of elements in which they differ. The distance d of the linear code is the minimum weight of its nonzero codewords, or equivalently, the minimum distance between distinct codewords. A linear code of length n, dimension k, and distance d is called an [n,k,d] code (or, more precisely, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [n,k,d]_{q}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [n,k,d]_{q}}</annotation>

</semantics>

</math><img src="./5eef76e1d6b74cc535236a6249e75afeea540ee3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.172ex; height:3.009ex;" alt="{\displaystyle [n,k,d]_{q}}" loading="lazy"> code).

We want to give <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{q}^{n}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{q}^{n}}</annotation>

</semantics>

</math><img src="./0a630603c6f2f8f58f5d1fb9ef1b9ad194e258a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:2.639ex; height:3.176ex;" alt="{\displaystyle \mathbb {F} _{q}^{n}}" loading="lazy"> the standard basis because each coordinate represents a "bit" that is transmitted across a "noisy channel" with some small probability of transmission error (a <a href="Binary_symmetric_channel" title="Binary symmetric channel">binary symmetric channel</a>). If some other basis is used then this model cannot be used and the Hamming metric does not measure the number of errors in transmission, as we want it to.

<div class="mw-heading mw-heading2"><h2 id="Generator_and_check_matrices">Generator and check matrices</h2></div>

As a <a href="Linear_subspace" title="Linear subspace">linear subspace</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{q}^{n}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{q}^{n}}</annotation>

</semantics>

</math><img src="./0a630603c6f2f8f58f5d1fb9ef1b9ad194e258a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:2.639ex; height:3.176ex;" alt="{\displaystyle \mathbb {F} _{q}^{n}}" loading="lazy">, the entire code C (which may be very large) may be represented as the <a href="Span_(linear_algebra)" class="mw-redirect" title="Span (linear algebra)">span</a> of a set of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> codewords (known as a <a href="Basis_(linear_algebra)" title="Basis (linear algebra)">basis</a> in <a href="Linear_algebra" title="Linear algebra">linear algebra</a>). These basis codewords are often collated in the rows of a matrix G known as a <a href="Generator_matrix" title="Generator matrix">generating matrix</a> for the code C. When G has the block matrix form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {G}}=[I_{k}\mid P]}">

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {G}}=[I_{k}\mid P]}</annotation>

</semantics>

</math><img src="./5b39eaa9d4bc1afb615e3e7c87e7f27ed430f802.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.248ex; height:2.843ex;" alt="{\displaystyle {\boldsymbol {G}}=[I_{k}\mid P]}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle I_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I_{k}}</annotation>

</semantics>

</math><img src="./d658e7f6b34dd1d3025a7c9a72efba5b9f46475d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.112ex; height:2.509ex;" alt="{\displaystyle I_{k}}" loading="lazy"> denotes the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\times k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\times k}</annotation>

</semantics>

</math><img src="./77bcf9346bcb189917b6b49c4331b4483f4a4a2c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.263ex; height:2.176ex;" alt="{\displaystyle k\times k}" loading="lazy"> identity matrix and P is some <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\times (n-k)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\times (n-k)}</annotation>

</semantics>

</math><img src="./d51ee3484090b09ef1b37bf5d836003e8c749c92.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.307ex; height:2.843ex;" alt="{\displaystyle k\times (n-k)}" loading="lazy"> matrix, then we say G is in standard form.

A matrix H representing a linear function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \phi :\mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n-k}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \phi :\mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n-k}}</annotation>

</semantics>

</math><img src="./484392e557c808d41b928fdc48db15ed81cb117d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:14.349ex; height:3.509ex;" alt="{\displaystyle \phi :\mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n-k}}" loading="lazy"> whose <a href="Kernel_(matrix)" class="mw-redirect" title="Kernel (matrix)">kernel</a> is C is called a <a href="Check_matrix" class="mw-redirect" title="Check matrix">check matrix</a> of C (or sometimes a parity check matrix). Equivalently, H is a matrix whose <a href="Null_space" class="mw-redirect" title="Null space">null space</a> is C. If C is a code with a generating matrix G in standard form, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {G}}=[I_{k}\mid P]}">

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {G}}=[I_{k}\mid P]}</annotation>

</semantics>

</math><img src="./5b39eaa9d4bc1afb615e3e7c87e7f27ed430f802.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.248ex; height:2.843ex;" alt="{\displaystyle {\boldsymbol {G}}=[I_{k}\mid P]}" loading="lazy">, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {H}}=[-P^{T}\mid I_{n-k}]}">

</mrow>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {H}}=[-P^{T}\mid I_{n-k}]}</annotation>

</semantics>

</math><img src="./e0803113fbe897fdac6c61f3ad26149897d2170a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.111ex; height:3.176ex;" alt="{\displaystyle {\boldsymbol {H}}=[-P^{T}\mid I_{n-k}]}" loading="lazy"> is a check matrix for C. The code generated by H is called the dual code of C. It can be verified that G is a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\times n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\times n}</annotation>

</semantics>

</math><img src="./8e173885ca0f29dd406df781144cd635276c68e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.446ex; height:2.176ex;" alt="{\displaystyle k\times n}" loading="lazy"> matrix, while H is a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n-k)\times n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n-k)\times n}</annotation>

</semantics>

</math><img src="./81d0ce9df55fbd0d24d52ac92f007cb08147ab87.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.491ex; height:2.843ex;" alt="{\displaystyle (n-k)\times n}" loading="lazy"> matrix.

Linearity guarantees that the minimum <a href="Hamming_distance" title="Hamming distance">Hamming distance</a> d between a codeword c0 and any of the other codewords c ≠ c0 is independent of c0. This follows from the property that the difference c − c0 of two codewords in C is also a codeword (i.e., an <a href="Element_(mathematics)" title="Element (mathematics)">element</a> of the subspace C), and the property that d(c, c0) = d(c − c0, 0). These properties imply that

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min _{c\in C,\ c\neq c_{0}}d(c,c_{0})=\min _{c\in C,\ c\neq c_{0}}d(c-c_{0},0)=\min _{c\in C,\ c\neq 0}d(c,0)=d.}</annotation>

</semantics>

</math><img src="./f245d1d0b4e45912c1614448d5a9a5bd724c3885.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:58.971ex; height:4.343ex;" alt="{\displaystyle \min _{c\in C,\ c\neq c_{0}}d(c,c_{0})=\min _{c\in C,\ c\neq c_{0}}d(c-c_{0},0)=\min _{c\in C,\ c\neq 0}d(c,0)=d.}" loading="lazy"></dd></dl>

In other words, in order to find out the minimum distance between the codewords of a linear code, one would only need to look at the non-zero codewords. The non-zero codeword with the smallest weight has then the minimum distance to the zero codeword, and hence determines the minimum distance of the code.

The distance d of a linear code C also equals the minimum number of linearly dependent columns of the check matrix H.

Proof: Because <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {H}}\cdot {\boldsymbol {c}}^{T}={\boldsymbol {0}}}">

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {H}}\cdot {\boldsymbol {c}}^{T}={\boldsymbol {0}}}</annotation>

</semantics>

</math><img src="./59a2e4e9bdd290d3e70dfcbbab04ae2dd641f328.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.083ex; height:2.676ex;" alt="{\displaystyle {\boldsymbol {H}}\cdot {\boldsymbol {c}}^{T}={\boldsymbol {0}}}" loading="lazy">, which is equivalent to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{i=1}^{n}(c_{i}\cdot {\boldsymbol {H_{i}}})={\boldsymbol {0}}}">

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i=1}^{n}(c_{i}\cdot {\boldsymbol {H_{i}}})={\boldsymbol {0}}}</annotation>

</semantics>

</math><img src="./eecbe07fcf648b44c7430a12984885001df63573.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:16.265ex; height:6.843ex;" alt="{\displaystyle \sum _{i=1}^{n}(c_{i}\cdot {\boldsymbol {H_{i}}})={\boldsymbol {0}}}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {H_{i}}}}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {H_{i}}}}</annotation>

</semantics>

</math><img src="./de05004cf99eb4f93e8af5f5dc388ae45e184682.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.18ex; height:2.509ex;" alt="{\displaystyle {\boldsymbol {H_{i}}}}" loading="lazy"> is the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i^{th}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i^{th}}</annotation>

</semantics>

</math><img src="./9c454bb35f050556d361ee85e06ca923b16a3bf4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.575ex; height:2.676ex;" alt="{\displaystyle i^{th}}" loading="lazy"> column of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {H}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {H}}}</annotation>

</semantics>

</math><img src="./73c9e11c17393610f4fc50c817c929d95349fa7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.386ex; height:2.176ex;" alt="{\displaystyle {\boldsymbol {H}}}" loading="lazy">. Remove those items with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i}=0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i}=0}</annotation>

</semantics>

</math><img src="./06dbc33495a748ad5067cb6ff07cba653cffaf2c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.067ex; height:2.509ex;" alt="{\displaystyle c_{i}=0}" loading="lazy">, those <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {H_{i}}}}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {H_{i}}}}</annotation>

</semantics>

</math><img src="./de05004cf99eb4f93e8af5f5dc388ae45e184682.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.18ex; height:2.509ex;" alt="{\displaystyle {\boldsymbol {H_{i}}}}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i}\neq 0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i}\neq 0}</annotation>

</semantics>

</math><img src="./bd8b02f63dd177fb17a45d4e0fdc6954826ac120.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.067ex; height:2.676ex;" alt="{\displaystyle c_{i}\neq 0}" loading="lazy"> are linearly dependent. Therefore, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> is at least the minimum number of linearly dependent columns. On another hand, consider the minimum set of linearly dependent columns <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{{\boldsymbol {H_{j}}}\mid j\in S\}}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{{\boldsymbol {H_{j}}}\mid j\in S\}}</annotation>

</semantics>

</math><img src="./05f6d169a538acecae0d9b9e991a19801dfa1ce8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:12.849ex; height:3.009ex;" alt="{\displaystyle \{{\boldsymbol {H_{j}}}\mid j\in S\}}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> is the column index set. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{i=1}^{n}(c_{i}\cdot {\boldsymbol {H_{i}}})=\sum _{j\in S}(c_{j}\cdot {\boldsymbol {H_{j}}})+\sum _{j\notin S}(c_{j}\cdot {\boldsymbol {H_{j}}})={\boldsymbol {0}}}">

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i=1}^{n}(c_{i}\cdot {\boldsymbol {H_{i}}})=\sum _{j\in S}(c_{j}\cdot {\boldsymbol {H_{j}}})+\sum _{j\notin S}(c_{j}\cdot {\boldsymbol {H_{j}}})={\boldsymbol {0}}}</annotation>

</semantics>

</math><img src="./c35f918554e1c0e266bd68400182df96f7a4a9b5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:46.301ex; height:7.343ex;" alt="{\displaystyle \sum _{i=1}^{n}(c_{i}\cdot {\boldsymbol {H_{i}}})=\sum _{j\in S}(c_{j}\cdot {\boldsymbol {H_{j}}})+\sum _{j\notin S}(c_{j}\cdot {\boldsymbol {H_{j}}})={\boldsymbol {0}}}" loading="lazy">. Now consider the vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {c'}}}">

<msup>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {c'}}}</annotation>

</semantics>

</math><img src="./ad3e4b2dcb9bfc46b88d7de0541d264fb002ce30.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.877ex; height:2.509ex;" alt="{\displaystyle {\boldsymbol {c'}}}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{j}'=0}">

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{j}'=0}</annotation>

</semantics>

</math><img src="./0abdd51d3d63d06e78fa606be7cab9cbe09d4ac5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:6.177ex; height:3.176ex;" alt="{\displaystyle c_{j}'=0}" loading="lazy"> if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j\notin S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j\notin S}</annotation>

</semantics>

</math><img src="./7f3d7bea9a2d042e11b262747f18ba254a6f421a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.027ex; width:5.325ex; height:2.676ex;" alt="{\displaystyle j\notin S}" loading="lazy">. Note <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {c'}}\in C}">

<msup>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {c'}}\in C}</annotation>

</semantics>

</math><img src="./1c98a74d8c8b2668ec78a6ca38829420dc08d39b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.484ex; height:2.509ex;" alt="{\displaystyle {\boldsymbol {c'}}\in C}" loading="lazy"> because <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {H}}\cdot {\boldsymbol {c'}}^{T}={\boldsymbol {0}}}">

</mrow>

<msup>

<msup>

</msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {H}}\cdot {\boldsymbol {c'}}^{T}={\boldsymbol {0}}}</annotation>

</semantics>

</math><img src="./f137a6d5f9634ffe9efbc42b38620412d57639f5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.767ex; height:3.009ex;" alt="{\displaystyle {\boldsymbol {H}}\cdot {\boldsymbol {c'}}^{T}={\boldsymbol {0}}}" loading="lazy"> . Therefore, we have <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d\leq wt({\boldsymbol {c'}})}">

<msup>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d\leq wt({\boldsymbol {c'}})}</annotation>

</semantics>

</math><img src="./dd462f57eddb44be78e1c6ce5130910915bcd5af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.505ex; height:3.009ex;" alt="{\displaystyle d\leq wt({\boldsymbol {c'}})}" loading="lazy">, which is the minimum number of linearly dependent columns in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {H}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {H}}}</annotation>

</semantics>

</math><img src="./73c9e11c17393610f4fc50c817c929d95349fa7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.386ex; height:2.176ex;" alt="{\displaystyle {\boldsymbol {H}}}" loading="lazy">. The claimed property is therefore proven.

<div class="mw-heading mw-heading2"><h2 id="Example:_Hamming_codes">Example: Hamming codes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Hamming_code" title="Hamming code">Hamming code</a></div>

As the first class of linear codes developed for error correction purpose, <a href="Hamming_code" title="Hamming code">Hamming codes</a> have been widely used in digital communication systems. For any positive integer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r\geq 2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r\geq 2}</annotation>

</semantics>

</math><img src="./514b8e859c803190ff03bb1b308e352195311171.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.31ex; height:2.343ex;" alt="{\displaystyle r\geq 2}" loading="lazy">, there exists a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [2^{r}-1,2^{r}-r-1,3]_{2}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [2^{r}-1,2^{r}-r-1,3]_{2}}</annotation>

</semantics>

</math><img src="./f4b7099796302beb1cea00796f3d9a67b448e08c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.745ex; height:2.843ex;" alt="{\displaystyle [2^{r}-1,2^{r}-r-1,3]_{2}}" loading="lazy"> Hamming code. Since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d=3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d=3}</annotation>

</semantics>

</math><img src="./58a4a6128b5cc1e25fcba3a16cbd9126b2d3e2fc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.477ex; height:2.176ex;" alt="{\displaystyle d=3}" loading="lazy">, this Hamming code can correct a 1-bit error.

Example : The linear block code with the following generator matrix and parity check matrix is a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [7,4,3]_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [7,4,3]_{2}}</annotation>

</semantics>

</math><img src="./499457f6464e18a49d7e72d66681299c4862829a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.903ex; height:2.843ex;" alt="{\displaystyle [7,4,3]_{2}}" loading="lazy"> Hamming code.

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {G}}={\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&0&1&1\\0&0&1&0&1&1&1\\0&0&0&1&1&0&1\end{pmatrix}},}</annotation>

</semantics>

</math><img src="./5d370698ad59ac24b23462851b3fda25f4820d6e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.671ex; width:32.698ex; height:12.509ex;" alt="{\displaystyle {\boldsymbol {G}}={\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&0&1&1\\0&0&1&0&1&1&1\\0&0&0&1&1&0&1\end{pmatrix}},}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {H}}={\begin{pmatrix}1&0&1&1&1&0&0\\1&1&\ 1&0&0&1&0\\0&1&1&1&0&0&1\end{pmatrix}}}">

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {H}}={\begin{pmatrix}1&0&1&1&1&0&0\\1&1&\ 1&0&0&1&0\\0&1&1&1&0&0&1\end{pmatrix}}}</annotation>

</semantics>

</math><img src="./e155c053be98634b9a831bbe6c00b8be5dad34bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.005ex; width:32.957ex; height:9.176ex;" alt="{\displaystyle {\boldsymbol {H}}={\begin{pmatrix}1&0&1&1&1&0&0\\1&1&\ 1&0&0&1&0\\0&1&1&1&0&0&1\end{pmatrix}}}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Example:_Hadamard_codes">Example: Hadamard codes</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Hadamard_code" title="Hadamard code">Hadamard code</a></div>

<a href="Hadamard_code" title="Hadamard code">Hadamard code</a> is a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [2^{r},r,2^{r-1}]_{2}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [2^{r},r,2^{r-1}]_{2}}</annotation>

</semantics>

</math><img src="./e698d84a6a5cfe250e1e1831a36917bc5f6dbc60.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.837ex; height:3.176ex;" alt="{\displaystyle [2^{r},r,2^{r-1}]_{2}}" loading="lazy"> linear code and is capable of correcting many errors. Hadamard code could be constructed column by column : the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i^{th}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i^{th}}</annotation>

</semantics>

</math><img src="./9c454bb35f050556d361ee85e06ca923b16a3bf4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.575ex; height:2.676ex;" alt="{\displaystyle i^{th}}" loading="lazy"> column is the bits of the binary representation of integer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">, as shown in the following example. Hadamard code has minimum distance <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{r-1}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{r-1}}</annotation>

</semantics>

</math><img src="./30c47034cc5f821de5d23f7648dc5fba876f6f99.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.237ex; height:2.676ex;" alt="{\displaystyle 2^{r-1}}" loading="lazy"> and therefore can correct <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{r-2}-1}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{r-2}-1}</annotation>

</semantics>

</math><img src="./6624d45afe13d5b0b1ae6ea0837e9911c5bb74fe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.24ex; height:2.843ex;" alt="{\displaystyle 2^{r-2}-1}" loading="lazy"> errors.

Example: The linear block code with the following generator matrix is a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [8,3,4]_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [8,3,4]_{2}}</annotation>

</semantics>

</math><img src="./25e2abe070a736c1d85fc3d68f41ad9d65cc9a85.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.903ex; height:2.843ex;" alt="{\displaystyle [8,3,4]_{2}}" loading="lazy"> Hadamard code:

<msub>

</mrow>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {G}}_{\mathrm {Had} }={\begin{pmatrix}0&0&0&0&1&\ 1&1&1\\0&0&1&1&0&0&1&1\\0&1&0&1&0&1&0&1\end{pmatrix}}}</annotation>

</semantics>

</math><img src="./f48afd81a8533c6c2564fa63868edae157751516.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.005ex; width:39.317ex; height:9.176ex;" alt="{\displaystyle {\boldsymbol {G}}_{\mathrm {Had} }={\begin{pmatrix}0&0&0&0&1&\ 1&1&1\\0&0&1&1&0&0&1&1\\0&1&0&1&0&1&0&1\end{pmatrix}}}" loading="lazy">.

<a href="Hadamard_code" title="Hadamard code">Hadamard code</a> is a special case of <a href="Reed%E2%80%93Muller_code" title="Reed–Muller code">Reed–Muller code</a>. If we take the first column (the all-zero column) out from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {G}}_{\mathrm {Had} }}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {G}}_{\mathrm {Had} }}</annotation>

</semantics>

</math><img src="./f3ca78d76d82631ea84fdd6c7d1c5aaf90be76dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.262ex; height:2.509ex;" alt="{\displaystyle {\boldsymbol {G}}_{\mathrm {Had} }}" loading="lazy">, we get <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [7,3,4]_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [7,3,4]_{2}}</annotation>

</semantics>

</math><img src="./61062d9e8384323c74a528929abb584e5c30caba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.903ex; height:2.843ex;" alt="{\displaystyle [7,3,4]_{2}}" loading="lazy"> simplex code, which is the dual code of Hamming code.

<div class="mw-heading mw-heading2"><h2 id="Nearest_neighbor_algorithm">Nearest neighbor algorithm</h2></div>

The parameter d is closely related to the error correcting ability of the code. The following construction/algorithm illustrates this (called the nearest neighbor decoding algorithm):

Input: A received vector v in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{q}^{n}.}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{q}^{n}.}</annotation>

</semantics>

</math><img src="./b3ce3fcf0b32ad2bee8682b297868d6634339a74.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:3.286ex; height:3.176ex;" alt="{\displaystyle \mathbb {F} _{q}^{n}.}" loading="lazy">

Output: A codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> closest to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy">, if any.

<ul><li>Starting with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=0}</annotation>

</semantics>

</math><img src="./43469ec032d858feae5aa87029e22eaaf0109e9c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.101ex; height:2.176ex;" alt="{\displaystyle t=0}" loading="lazy">, repeat the following two steps.</li>

<li>Enumerate the elements of the ball of (Hamming) radius <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> around the received word <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy">, denoted <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B_{t}(v)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B_{t}(v)}</annotation>

</semantics>

</math><img src="./81f6258c1d7b73b2adc93cb6b2ddcc79093c24c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.527ex; height:2.843ex;" alt="{\displaystyle B_{t}(v)}" loading="lazy">.

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B_{t}(v)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B_{t}(v)}</annotation>

</semantics>

</math><img src="./81f6258c1d7b73b2adc93cb6b2ddcc79093c24c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.527ex; height:2.843ex;" alt="{\displaystyle B_{t}(v)}" loading="lazy">, check if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy">. If so, return <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"> as the solution.</li></ul></li>

<li>Increment <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">. Fail only when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t>(d-1)/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t>(d-1)/2}</annotation>

</semantics>

</math><img src="./ae05ce0e484495be4dc9bcff1151de24d6d0147f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.291ex; height:2.843ex;" alt="{\displaystyle t>(d-1)/2}" loading="lazy"> so enumeration is complete and no solution has been found.</li></ul>

We say that a linear <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">-error correcting if there is at most one codeword in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B_{t}(v)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B_{t}(v)}</annotation>

</semantics>

</math><img src="./81f6258c1d7b73b2adc93cb6b2ddcc79093c24c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.527ex; height:2.843ex;" alt="{\displaystyle B_{t}(v)}" loading="lazy">, for each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{q}^{n}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{q}^{n}}</annotation>

</semantics>

</math><img src="./0a630603c6f2f8f58f5d1fb9ef1b9ad194e258a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:2.639ex; height:3.176ex;" alt="{\displaystyle \mathbb {F} _{q}^{n}}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Popular_notation">Popular notation</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Block_code#Popular_notation" title="Block code">Block code § Popular notation</a></div>

<a href="Code" title="Code">Codes</a> in general are often denoted by the letter C, and a code of length n and of <a href="Dimension_(linear_algebra)" class="mw-redirect" title="Dimension (linear algebra)">rank</a> k (i.e., having n code words in its basis and k rows in its generating matrix) is generally referred to as an (n, k) code. Linear block codes are frequently denoted as [n, k, d] codes, where d refers to the code's minimum Hamming distance between any two code words.

(The [n, k, d] notation should not be confused with the (n, M, d) notation used to denote a non-linear code of length n, size M (i.e., having M code words), and minimum Hamming distance d.)

<div class="mw-heading mw-heading2"><h2 id="Singleton_bound">Singleton bound</h2></div>

Lemma (<a href="Singleton_bound" title="Singleton bound">Singleton bound</a>): Every linear [n,k,d] code C satisfies <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k+d\leq n+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k+d\leq n+1}</annotation>

</semantics>

</math><img src="./39463061e873b658c8e124e85e178fadbdb850ee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:13.764ex; height:2.343ex;" alt="{\displaystyle k+d\leq n+1}" loading="lazy">.

A code C whose parameters satisfy k +d = n + 1 is called maximum distance separable or MDS. Such codes, when they exist, are in some sense best possible.

If C1 and C2 are two codes of length n and if there is a permutation p in the <a href="Symmetric_group" title="Symmetric group">symmetric group</a> Sn for which (c1,...,cn) in C1 if and only if (cp(1),...,cp(n)) in C2, then we say C1 and C2 are permutation equivalent. In more generality, if there is an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\times n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\times n}</annotation>

</semantics>

</math><img src="./59d2b4cb72e304526cf5b5887147729ea259da78.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.63ex; height:1.676ex;" alt="{\displaystyle n\times n}" loading="lazy"> <a href="Monomial_matrix" class="mw-redirect" title="Monomial matrix">monomial matrix</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M\colon \mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M\colon \mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n}}</annotation>

</semantics>

</math><img src="./9bbc03238cc0c9aac68cf30aa22c22867ab82bc2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:12.368ex; height:3.176ex;" alt="{\displaystyle M\colon \mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n}}" loading="lazy"> which sends C1 isomorphically to C2 then we say C1 and C2 are equivalent.

Lemma: Any linear code is permutation equivalent to a code which is in standard form.

<div class="mw-heading mw-heading2"><h2 id="Bonisoli's_theorem">Bonisoli's theorem</h2></div>

A code is defined to be equidistant if and only if there exists some constant d such that the distance between any two of the code's distinct codewords is equal to d.<a href="#cite_note-4">[4]</a> In 1984 Arrigo Bonisoli determined the structure of linear one-weight codes over finite fields and proved that every equidistant linear code is a sequence of <a href="Dual_code" title="Dual code">dual</a> <a href="Hamming_code" title="Hamming code">Hamming codes</a>.<a href="#cite_note-5">[5]</a>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

Some examples of linear codes include:

/* start https://en.wikipedia.org/ */

.mw-parser-output .div-col{margin-top:0.3em;column-width:30em}.mw-parser-output .div-col-small{font-size:90%}.mw-parser-output .div-col-rules{column-rule:1px solid #aaa}.mw-parser-output .div-col dl,.mw-parser-output .div-col ol,.mw-parser-output .div-col ul{margin-top:0}.mw-parser-output .div-col li,.mw-parser-output .div-col dd{page-break-inside:avoid;break-inside:avoid-column}

/* end https://en.wikipedia.org/ */

</style><div class="div-col" style="column-width: 27em;">

<ul><li><a href="Repetition_code" title="Repetition code">Repetition code</a></li>

<li><a href="Parity_code" class="mw-redirect" title="Parity code">Parity code</a></li>

<li><a href="Cyclic_code" title="Cyclic code">Cyclic code</a></li>

<li><a href="Hamming_code" title="Hamming code">Hamming code</a></li>

<li><a href="Golay_code_(disambiguation)" class="mw-redirect mw-disambig" title="Golay code (disambiguation)">Golay code</a>, both the <a href="Binary_Golay_code" title="Binary Golay code">binary</a> and <a href="Ternary_Golay_code" title="Ternary Golay code">ternary</a> versions</li>

<li><a href="Polynomial_code" title="Polynomial code">Polynomial codes</a>, of which <a href="BCH_code" title="BCH code">BCH codes</a> are an example</li>

<li><a href="Reed%E2%80%93Solomon_error_correction" title="Reed–Solomon error correction">Reed–Solomon codes</a></li>

<li><a href="Reed%E2%80%93Muller_code" title="Reed–Muller code">Reed–Muller code</a></li>

<li><a href="Algebraic_geometry_code" title="Algebraic geometry code">Algebraic geometry code</a></li>

<li><a href="Binary_Goppa_code" title="Binary Goppa code">Binary Goppa code</a></li>

<li><a href="Low-density_parity-check_codes" class="mw-redirect" title="Low-density parity-check codes">Low-density parity-check codes</a></li>

<li><a href="Expander_code" title="Expander code">Expander code</a></li>

<li><a href="Multidimensional_parity-check_code" title="Multidimensional parity-check code">Multidimensional parity-check code</a></li>

<li><a href="Toric_code" title="Toric code">Toric code</a></li>

<li><a href="Turbo_code" title="Turbo code">Turbo code</a></li>

<li><a href="Locally_recoverable_code" title="Locally recoverable code">Locally recoverable code</a></li></ul>

</div>

<div class="mw-heading mw-heading2"><h2 id="Generalization">Generalization</h2></div>

<a href="Hamming_space" title="Hamming space">Hamming spaces</a> over non-field alphabets have also been considered, especially over <a href="Finite_ring" title="Finite ring">finite rings</a>, most notably <a href="Galois_ring" title="Galois ring">Galois rings</a> over <a href="Modular_arithmetic" title="Modular arithmetic">Z4</a>. This gives rise to <a href="Module_(mathematics)" title="Module (mathematics)">modules</a> instead of vector spaces and ring-linear codes (identified with <a href="Submodule" class="mw-redirect" title="Submodule">submodules</a>) instead of linear codes. The typical metric used in this case the <a href="Lee_distance" title="Lee distance">Lee distance</a>. There exist a <a href="Gray_isometry" class="mw-redirect" title="Gray isometry">Gray isometry</a> between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} _{2}^{2m}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} _{2}^{2m}}</annotation>

</semantics>

</math><img src="./c95e46f6e851988f7bf14fed668b93831351f148.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.047ex; height:3.176ex;" alt="{\displaystyle \mathbb {Z} _{2}^{2m}}" loading="lazy"> (i.e. GF(22m)) with the Hamming distance and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} _{4}^{m}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} _{4}^{m}}</annotation>

</semantics>

</math><img src="./17ffb5c4a91673878356885f5d3401856c907eef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.225ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} _{4}^{m}}" loading="lazy"> (also denoted as GR(4,m)) with the Lee distance; its main attraction is that it establishes a correspondence between some "good" codes that are not linear over <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} _{2}^{2m}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} _{2}^{2m}}</annotation>

</semantics>

</math><img src="./c95e46f6e851988f7bf14fed668b93831351f148.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.047ex; height:3.176ex;" alt="{\displaystyle \mathbb {Z} _{2}^{2m}}" loading="lazy"> as images of ring-linear codes from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} _{4}^{m}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} _{4}^{m}}</annotation>

</semantics>

</math><img src="./17ffb5c4a91673878356885f5d3401856c907eef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.225ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} _{4}^{m}}" loading="lazy">.<a href="#cite_note-Greferath2009-6">[6]</a><a href="#cite_note-7">[7]</a><a href="#cite_note-Lint1999-8">[8]</a>

Some authors have referred to such codes over rings simply as linear codes as well.<a href="#cite_note-DoughertyFacchini2015-9">[9]</a>

<ul><li><a href="Decoding_methods" title="Decoding methods">Decoding methods</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFWilliam_E._Ryan_and_Shu_Lin2009" class="citation book cs1">William E. Ryan and Shu Lin (2009). <a rel="nofollow" class="external text" href="https://archive.org/details/channelcodesclas00ryan">Channel Codes: Classical and Modern</a>. Cambridge University Press. p. <a rel="nofollow" class="external text" href="https://archive.org/details/channelcodesclas00ryan/page/n21">4</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-84868-8</bdi>.</cite>

</li>

<li id="cite_note-DrMacKayECC-2"><a href="#cite_ref-DrMacKayECC_2-0">^</a> <cite id="CITEREFMacKay2003" class="citation book cs1"><a href="David_J.C._MacKay" class="mw-redirect" title="David J.C. MacKay">MacKay, David, J.C.</a> (2003). <a rel="nofollow" class="external text" href="http://www.inference.phy.cam.ac.uk/itprnn/book.pdf">Information Theory, Inference, and Learning Algorithms</a> (PDF). <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. p. 9. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2003itil.book.....M">2003itil.book.....M</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780521642989</bdi>. <q>In a linear block code, the extra <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N-K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N-K}</annotation>

</semantics>

</math><img src="./af4f62a05585d80e2056fb27022b11d0028e4e1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.97ex; height:2.343ex;" alt="{\displaystyle N-K}" loading="lazy"> bits are linear functions of the original <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy"> bits; these extra bits are called parity-check bits</q></cite><code class="cs1-code">{{cite book}}</code>: CS1 maint: multiple names: authors list (link)

</li>

<li id="cite_note-Cover_and_Thomas-3"><a href="#cite_ref-Cover_and_Thomas_3-0">^</a> <cite id="CITEREFThomas_M._Cover_and_Joy_A._Thomas1991" class="citation book cs1">Thomas M. Cover and Joy A. Thomas (1991). <a rel="nofollow" class="external text" href="https://archive.org/details/elementsofinform0000cove/page/210">Elements of Information Theory</a>. John Wiley & Sons, Inc. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/elementsofinform0000cove/page/210">210–211</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-471-06259-2</bdi>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFEtzion,_TuviRaviv,_Netanel2013" class="citation arxiv cs1">Etzion, Tuvi; Raviv, Netanel (2013). "Equidistant codes in the Grassmannian". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1308.6231">1308.6231</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/math.CO">math.CO</a>].</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFBonisoli,_A.1984" class="citation journal cs1">Bonisoli, A. (1984). "Every equidistant linear code is a sequence of dual Hamming codes". Ars Combinatoria. 18: 181–186.</cite>

</li>

<li id="cite_note-Greferath2009-6"><a href="#cite_ref-Greferath2009_6-0">^</a> <cite id="CITEREFMarcus_Greferath2009" class="citation book cs1">Marcus Greferath (2009). "An Introduction to Ring-Linear Coding Theory". In Massimiliano Sala; Teo Mora; Ludovic Perret; Shojiro Sakata; Carlo Traverso (eds.). Gröbner Bases, Coding, and Cryptography. Springer Science & Business Media. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-93806-4</bdi>.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.encyclopediaofmath.org/index.php/Main_Page">"Encyclopedia of Mathematics"</a>. www.encyclopediaofmath.org.</cite>

</li>

<li id="cite_note-Lint1999-8"><a href="#cite_ref-Lint1999_8-0">^</a> <cite id="CITEREFJ.H._van_Lint1999" class="citation book cs1">J.H. van Lint (1999). <a rel="nofollow" class="external text" href="https://archive.org/details/introductiontoco0000lint_a3b9">Introduction to Coding Theory</a> (3rd ed.). Springer. Chapter 8: Codes over ℤ4. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-64133-9</bdi>.</cite>

</li>

<li id="cite_note-DoughertyFacchini2015-9"><a href="#cite_ref-DoughertyFacchini2015_9-0">^</a> <cite id="CITEREFS.T._DoughertyJ.-L._KimP._Sole2015" class="citation book cs1">S.T. Dougherty; J.-L. Kim; P. Sole (2015). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=psrXBgAAQBAJ&pg=PA80">"Open Problems in Coding Theory"</a>. In Steven Dougherty; Alberto Facchini; Andre Gerard Leroy; Edmund Puczylowski; Patrick Sole (eds.). Noncommutative Rings and Their Applications. American Mathematical Soc. p. 80. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4704-1032-2</bdi>.</cite>

</li>

</ol></div>

<div class="mw-heading mw-heading3"><h3 id="Bibliography">Bibliography</h3></div>

<ul><li><cite id="CITEREFJ._F._HumphreysM._Y._Prest2004" class="citation book cs1">J. F. Humphreys; M. Y. Prest (2004). Numbers, Groups and Codes (2nd ed.). Cambridge University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-511-19420-7</bdi>.</cite> Chapter 5 contains a more gentle introduction (than this article) to the subject of linear codes.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20070927213247/http://jason.mchu.com/QCode/index.html">q-ary code generator program</a></li>

<li><a rel="nofollow" class="external text" href="http://www.codetables.de/">Code Tables: Bounds on the parameters of various types of codes</a>, IAKS, Fakultät für Informatik, Universität Karlsruhe (TH)]. Online, up to date table of the optimal binary codes, includes non-binary codes.</li>

<li><a rel="nofollow" class="external text" href="http://z4codes.info/">The database of Z4 codes</a> Online, up to date database of optimal Z4 codes.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-11-28" href="https://en.wikipedia.org/wiki/?title=Linear_code&oldid=1259978043">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>